/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-07-13
 * Time: 12:44
 */
public class test3 {
    // 单词搜索

    int m,n;
    int[] dx = {0,0,1,-1};
    int[] dy = {1,-1,0,0};
    boolean[][] vis;
    char[] word;

    public boolean exist(String[] board,String _word){
        m = board.length;
        n = board[0].length();
        vis = new boolean[m][n];
        word = _word.toCharArray();
        for(int i=0;i<m;i++){
            for (int j=0;j<n;j++){
                // 如果这个位置的字符等于单词的首字母，就从这个位置开始
                if(board[i].charAt(j)==word[0]){
                    if(dfs(board,i,j,0)==true){
                        return true;
                    }
                }
            }
        }
        return false;
    }

    public boolean dfs(String[] board,int i,int j,int pos){
        // 出递归的条件
        if(pos== word.length-1){
            return true;
        }
        vis[i][j] = true;
        for (int k=0;k<4;k++){
            int x = i+dx[k];
            int y = j+dy[k];
            if(x>=0 && x<m && y>=0 && y<n && !vis[x][y] && board[x].charAt(y)==word[pos+1]){
                if(dfs(board,x,y,pos+1)){
                    return true;
                }
            }
        }
        vis[i][j] =false;
        return false;
    }
}
